14. Longest Common Prefix

題目描述：

請編寫一個函數來查找字符串陣列中的最長公共前綴。如果不存在公共前綴，則返回空字符串 ""。
Example 1:

• Input: strs = ["flower","flow","flight"]
• Output: "fl"

解題思路
字串的比較問題在 LeetCode 上是常見的題型。通常，從第一個字符串開始，依次與後面的字符串進行比較，是最常見的解法之一，這種方法也被稱為水平掃描法。
我們可以取第一個字串作為初始的 prefix，然後將其與第二個字串進行比較，檢查是否滿足公共前綴的條件（在這裡可以使用 JavaScript 的 indexOf 方法）。如果不滿足公共前綴的要求，就將 prefix 縮減最後一個字符（在這裡可以使用 JavaScript 的 substring 方法），然後再次進行比對，直到找到公共前綴為止。依此類推，將所有字串都與當前的 prefix 進行比較，最後剩下的 prefix 就是最長的公共前綴。

var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";

    let prefix = strs[0];

    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            if (prefix === "") return "";
        }
    }

    return prefix;
};

時間複雜度：O(n * m)，其中 n 是字串陣列的長度，m 是字串的平均長度。在最壞的情況下，需要比較 n 個字串，每個字串比較 m 次。
空間複雜度：O(1)，我們只使用了常數空間來存儲變數。

除了上述的解法之外，還有另一種解法是一次比較所有字串，從第一個字符開始，逐個字符地比較，直到發現不匹配的字符或者遍歷到某個字串的結尾。這種方法也被稱為垂直掃描法，因為它是按字符的位置逐個比較所有字串，而不是逐個字串比較。

var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";

    for (let i = 0; i < strs[0].length; i++) {
        const char = strs[0][i];

        for (let j = 1; j < strs.length; j++) {
            if (i >= strs[j].length || strs[j][i] !== char) {
                return strs[0].substring(0, i);
            }
        }
    }

    return strs[0];
};

時間複雜度：O(n * m)，其中 n 是字串陣列的長度，m 是字串中最短的長度。在最壞的情況下，需要比> 較所有字串的每個字符。
空間複雜度：O(1)，我們只使用了常數空間來存儲變數。

總結:
無論是水平掃描法還是垂直掃描法，這兩個方法在時間和空間複雜度上幾乎沒有區別，都是 O(n * m) 的時間複雜度和 O(1) 的空間複雜度。然而，稍微思考一下可以發現，垂直掃描法的速度可能會比水平掃描法更快找到公共前綴，因為它一旦發現不匹配的字符便會立即停止比較並退出迴圈。不論如何，這兩種方法都值得掌握，相信這將有助於提升讀者的程式設計能力。對於這道題，我們可以將其歸類為「string」，因為解題過程中需要熟悉和掌握字串的 API（如 indexOf 和 substring）。在解 LeetCode 問題之前，建議大家先複習一下自己熟悉語言中與字串處理相關的 API 使用方法，這樣在面對字串相關的 LeetCode 問題時，能夠更加冷靜應對，並找到最佳解答。